#include <string>

using std::string;

class Solution {
public:
    string addBinary(string a, string b) {
        int i = a.size() - 1;
        int j = b.size() - 1;
        int jin = '0';
        int offset = '0' * 2;
        string ret = "";
        while (i >= 0 && j >= 0) {
            jin = jin + a[i] + b[j] - offset;
            ret = (char)(jin % 2 + '0') + ret;
            jin = (jin >= '2') ? '1' : '0';
            i--;
            j--;
        }
        offset = '0';
        while (i >= 0) {
            jin = jin + a[i] - offset;
            ret = (char)(jin % 2 + '0') + ret;
            jin = (jin >= '2') ? '1' : '0';
            i--;
        }
        while (j >= 0) {
            jin = jin + b[j] - offset;
            ret = (char)(jin % 2 + '0') + ret;
            jin = (jin >= '2') ? '1' : '0';
            j--;
        }
        if (jin > '0') {
            ret = '1' + ret;
        }
        return ret;
    }
};